import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/22 20:16
 * @description 思路：由于数据范围不是很大，直接用计数数组，奇数下标非递减，为逆序遍历，偶数下标非递增，为正序遍历即可
 */
public class Solution2 {
    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        int[] nums = {4, 1, 2, 3};
        solution.sortEvenOdd(nums);
    }
    public int[] sortEvenOdd(int[] nums) {
        int n = nums.length;
        int[] odd = new int[101], even = new int[101];
        for(int i = 0; i < n; ++i) {
            if (i % 2 == 0) {
                even[nums[i]]++;
            }else {
                odd[nums[i]]++;
            }
        }
        // 奇数下标从1开始
        int index = 1;
        for (int i = 100; i >= 0; i--) {
            while (odd[i] > 0) {
                nums[index] = i;
                index += 2;
                odd[i]--;
            }
        }
        index = 0;
        for (int i = 0; i<= 100; i++) {
            while (even[i] > 0) {
                nums[index] = i;
                index += 2;
                even[i]--;
            }
        }
        return nums;
    }
}